import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=433 lang=java
 *
 * [433] 最小基因变化
 */

// @lc code=start
class Solution {
    public int minMutation(String start, String end, String[] bank) {

        Set<String> set = new HashSet<>(Arrays.asList(bank));
        if (!set.contains(end))  {
            return -1;
        }

        char[] four = {'A','C','G','T'};
        Queue<String> queue = new LinkedList<>();

        queue.offer(start);
        set.remove(start);
        int step = 0;

        while (!queue.isEmpty()) {
            step++;
            for (int m = 0, len = queue.size(); m < len; m++) {
                char[] tempStringChars = queue.poll().toCharArray();
                for (int i = 0; i < tempStringChars.length; i++) {
                    char oldChar = tempStringChars[i];
                    for (int j = 0; j < 4; j++) {
                        tempStringChars[i] = four[j];
                        String newGenetic = new String(tempStringChars);
                        if (end.equals(newGenetic)) {
                            return step;
                        } else if(set.contains(newGenetic)) {
                            set.remove(newGenetic);
                            queue.offer(newGenetic);
                        }
                    }
                    tempStringChars[i] = oldChar;
                }
            }
        }
        return -1;
    }
}
// @lc code=end

